
題目解析:給一個整數陣列,題目要求把所有的0都移到陣列的最後面,同時保持其他非零元素原本的相對順序,而且要求在原地(in-place)修改陣列,不能複製一份新的陣列
解題思路:設一個指標i從0開始,然後用j去跑遍整個陣列,只要nums[j]不是0,就把nums[j]和nums[i]交換,交換完i再往後移一格,這樣跑完一輪之後,所有非零的元素就會被依序集中到陣列前面,剩下的位置自然就會是0
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int i = 0;
for(int j=0; j<nums.size(); j++){
if(nums[j] != 0){
swap(nums[j], nums[i]);
i++;
}
}
}
};

題目解析:給兩個字串s跟t,題目要求判斷s是不是t的子序列,也就是s裡面的字元能不能依照原本的順序,在t裡面依序找到,中間可以跳過其他字元
解題思路:設一個q紀錄目前搜尋到t的哪個位置,然後跑第一層迴圈去遍歷s的每個字元,內層再從q開始往後找t,只要找到相同的字元,就把q更新成該位置+1,並且讓ans加1,最後判斷ans有沒有等於s的長度,如果相等代表s裡面的每個字元都有依序在t裡面找到,回傳1,反之則回傳0
class Solution {
public:
bool isSubsequence(string s, string t) {
int q = 0, ans = 0;
for(int i=0; i<s.size(); i++){
for(int j=q; j<t.size(); j++){
if(s[i] == t[j]){
q = j + 1;
ans++;
break;
}
}
}
if(ans == s.size()) return 1;
return 0;
}
};

題目解析:給一個陣列height,每個元素代表一條垂直線的高度,題目要求從裡面選兩條線,跟x軸一起組成一個容器,求這個容器能裝的最大水量
解題思路:設兩個指標i跟j,分別指向陣列的最前面跟最後面,然後開始跑迴圈,每次都用(j-i)乘上兩條線裡面比較矮的那條,去更新ans,接著判斷height[i]跟height[j]誰比較矮,比較矮的那邊就往中間移動,因為容器的水量是取決於較矮的那條線,移動較高的那邊不可能讓水量變大,所以只移動較矮的那邊才有機會找到更大的面積,直到i跟j相遇為止
class Solution {
public:
int maxArea(vector<int>& height) {
int ans = 0;
int i = 0, j = height.size()-1;
while(i != j){
ans = max(ans, (j-i)*min(height[i], height[j]));
if(height[i] <= height[j]) i++;
else j--;
}
return ans;
}
};